package com.xy6.algo.dynamic;

/**
 * 最长上升子序列
 * <pre>
 * 百练2757
 * 一个数的序列ai，当a1 < a2 < ... < aS的时候，我们称这个序列是上升的。
 * 对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，
 * 这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)， 
 * 有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。
 * 这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。
 * 你的任务，就是对于给定的序列，求出最长上升子序列的长度。
 * 
 * 求解该问题，关键在于找到正确的子问题，否则可能走向歧途，找不到求解方法。
 * 
 * 找子问题：
 * 求前n个字符的最长上升子序列的长度 为子问题，但该子问题不具有“后效性”。
 * 假设F(n)=x，计算F(n+1)时，不仅与F(n)有关，还与达到F(n)的过程有关（最长子序列可能有多个），不符合“无后继性”。
 * 以第n个字符结尾子串的最长上升子序列的长度 为子问题，该子问题具有“后效性”
 * 
 * 动态规划的无后效性：
 * 当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，
 * 和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
 * 
 * 状态转移方程：
 * maxlen(n)=
 * 如果存在1<i<n、a[i]<a[n]，则结果为max(manlen(i)) + 1；
 * 如果不存在1<i<n、a[i]<a[n]，则结果为1；
 * 
 * max=max(maxlen(i))，1=<i<=n
 * </pre>
 * 
 * 
 * @author zhang
 * @since 2017-11-12
 */
public class UpLCS {

	/**
	 * 计算一个字符串的最长上升子序列的长度
	 * 
	 * @param s
	 * @return
	 */
	public static int calc(String s){
		int[] len = new int[s.length()];
		int maxTemp = 0;
		int max = 0;
		for (int i = 0; i < s.length(); i++) {
			maxTemp = 0;
			for (int j = 0; j < i; j++) {
				if(s.charAt(j) < s.charAt(i) && len[j] > maxTemp){
					maxTemp = len[j];
				}
			}
			len[i] = maxTemp + 1;
			
			if(len[i] > max){
				max = len[i];
			}
		}
		return max;
	}
	
}
